The present invention relates to a prime interleaver used for W-CDMA in the IMT 2000 (third-generation mobile communication system), and more particularly, to an interleaving sequence generator, an interleaver, a turbo encoder, and a turbo decoder, having a reduced memory for the interleaving sequence generator.
The wideband CDMA (W-CDMA) is standardized as one of radio access networks (RANs) in the third-generation mobile communication system (IMT 2000). An internal interleaver for turbo coding, so-called prime interleaver is standardized. This primer interleaver is disclosed in detail in “3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Multiplexing and channel coding (FDD) (Release 1999) 3G TS25.212 V3.3.0 (2000-06), Section 4.2.3.2.3 “Turbo code internal interleaver” pp. 16–20”.
The turbo encoder comprises a plurality of component encoders. The interleaver decorrelation the parity sequences from the component encoders. The component encoders are concatenated via the interleaver. The interleaver plays an important role in achieving good performance of turbo coding.
FIG. 15 is a diagram showing an example of the structure of a conventional turbo encoder. Referring to FIG. 15, the turbo encoder comprises a plurality of recursive systematic convolutional encoders 1502 and 1503, and an interleaver 1501. The recursive systematic convolutional encoders 1502 and 1503 comprise an adder and a unit delay element. An information bit, a parity bit 1, and a parity bit 2 are output every bit of information series that is inputted to the turbo encoder. The interleaver 1501 is inserted in front of the component encoder 1503 so as to decrease the correlation between the parity bit 1 and the parity bit 2.
FIG. 16 is a diagram showing an example of the structure of a conventional turbo decoder. The turbo decoder comprises two soft input/soft output decoder (also referred to as soft-in/soft-out decoders, hereinafter, abbreviated to SISOs) 1603 and 1604, two interleavers 1601 and 1602, and two deinterleavers 1606 and 1607 which restores the sequence to its original order. A splitter 1605 splits parity sequence 1 and 2 into the corresponding SISOs, and a detector 1608 detects that the finally-obtained soft output data is subjected to the hard decision as binary data.
FIG. 17 shows an example of the conventional interleaver for permuting based on the unit of bit data in the interleaving sequence stored (stored as an interleave pattern table) in a RAM. In data series 1701 for interleaving, the data series is permuted in the bit sequence by a RAM 1702 which stores the interleaving sequence based on the interleaving pattern table, and thus data series 1703 after interleaving is obtained.
As shown by reference numeral 1702, in the relationship between an output of the RAM 1702 and the interleaving pattern table, from the pattern table having R blocks with a length p based on a prime p, data is read in accordance with the longitudinal sequence of 0, 8, 4, 12, 2, . . . as shown by an arrow so as to obtain the data series 1703 after interleaving.
According to the standard 3G TS 25.212 V3.3.0 (2000-06) of the IMT 2000 (W-CDMA), 5075 types of interleaving patterns must be provided with the interleaving length of 1 to 40 to 5114 bits based on the unit of bit for various multi-media service. The pattern table corresponding to the entire interleaving lengths requires the numerous memory capacity and this it not realistic. The particle “3G TS25.212 V3.3.0 (2000-06) or Turbo code internal interleaver p. 16 to p. 20 in 4.2.3.2.3 section” discloses a scheme for generating the patterns by a predetermined operation in accordance with the interleaving lengths, instead of storing the entire types of patterns.
In the prime interleaver disclosed in the particle “3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Multiplexing and channel coding (FDD) (Release 1999) 3G TS 25.212 V3.3.0 (2000-06) or V4.0.0 (2000-12) (Section 4.2.3.2.3 “Turbo code internal interleaver” pp. 16–20)”, when the data length is p based on the prime p and the number of blocks is R, and the base sequence S(j) for intra-row sequence permutation is obtained as follows by using a characteristic p and a primitive root ν on the finite field (intra-row permutation processing).s(j)=[ν·s(j−1)]mod p, j=1,2, . . . (p−2), and s(0)=1 (1)This is shown as Table. Next, R numbers of q(i) relatively prime to a number (p−1) obtained by subtracting one from the characteristic on the finite field are obtained. Finally, the sequence of rows is permuted based on the unit of row (inter-row permutation processing). The inter-row permutation is executed based on a predetermined pattern T(i). As the interlacing pattern in this case, a lattice pattern for increasing the free distance of the intra-rows is used.
In the i-th intra-row permutation, the following processing is executed.Ui(j)=s([j·ri]mod(p−1)), j=0, 1, 2, . . . , (p−2), and Ui(p−1)=0, (2)where, Ui(j) indicates the bit position before permutation, corresponding to the output position after the j-th intra-row permutation of the i-th row before the permutation, an equation of rT(i)=q(i) is established, and T(i) is the position of the i-th row before the above-defined permutation.
One example of the data length K=257 will be described. When the number of rows R in the two-dimensional matrix is 20, the number of columns p expressed by the prime p is 257/20=12.85. Consequently, the prime p that is not less than 12.85 and is the closet is 13. When the characteristic is 13, a primitive root ν is 2 on the finite field.
Then, the base sequence S(j) for inter-row permutation is derived by using the primitive root ν=2 based on the formula (1). If p=13 and ν=2, then,{s(j)}={1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 0}Finally, zero is inserted.
Next, in the above-mentioned example in the case of p=13, R=20 numbers of q(i) relatively prime to the number (p−1) obtained by subtracting one from the characteristic on the finite field are obtained. Consequently, the following result is obtained.{q(i)}={1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79}
Finally, based on the above formula (2), the inter-row permutation processing is performed with the row as a unit based on the predetermined pattern. The permutation pattern between the rows is obtained for increasing the free distance in the case of R=20. That is,Par1:{T(i)}={19, 9, 14, 4, 0, 2, 5, 7, 12, 18, 10, 8, 13, 17, 3, 1, 16, 6, 15, 11}.
Further, rT(i)=q(i), then,rT(1)=q(1)=1=r19rT(2)=q(2)=7=r9rT(3)=q(3)=11=r14:rT(19)=q(19)=73=r15rT(20)=q(20)=79=r11
The bit position Ui(j) is obtained by substituting the above values into the formula (2).
According to the above-mentioned conventional art, the bit position Ui(j) is calculated by software processing such as DSP (digital signal processor) or the like. In addition, the resultant data is transferred to the large-scale RAM 1702 shown in FIG. 17 for the interleaving processing.
Meanwhile, in the turbo decoder, the iterated decoding is performed. For example, in the case of decoding the received data of 2 Mbps with 8 iterations, the access to the above-mentioned interleaving sequence requires the fast operation, e.g., tens MHz. In order to respond to the requirement, the pattern generated in accordance with the above calculations is temporarily stored in a fast memory, and the memory structure needs the access having tens MHz.
However, the capacity of the memory (RAM) requires 66,482 bits (=5,114×13 bits), and greatly shares the turbo decoder. Further, it is necessary to transfer the data to the RAM for interleaving in the turbo decoder which actually performs the processing of the patterns generated based on the above calculations and the interface further needs the transfer of another data. Thus, there is a bottleneck on the interface.
Further, when the variable-rate function is provided, the interleaving length is frequently changed. In this case, the bottle neck on the interface further becomes serious and there is a problem that the rate does not follow the transfer rate in the multi-media service.
As mentioned above, the internal interleaver in the turbo decoder used for the mobile communication system corresponding to various multi-media services needs various interleaving lengths. Therefore, various interleaving patterns are necessary and a numerous memory capacity is required. Further, the fast data needs to temporarily store the interleaving pattern in a fast memory and, then, the fast memory capacity is necessary. This increases the circuit scale. Further, the service having a variable-rate function has the interface congestion due to the parameter transfer.